package array;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class FindAllDuplicatesInAnArray442 {

    @Test
    public void test() {
        findDuplicates(new int[]{4,3,2,7,8,2,3,1});
        findDuplicates(new int[]{3, 2, 2, 1});
        findDuplicates(new int[]{3, 2, 1, 1});
        findDuplicates(new int[]{3, 2, 4, 1});
        findDuplicates(new int[]{1, 1, 2});
    }

    public List<Integer> findDuplicates(int[] n) {
        List<Integer> dups = new ArrayList<>(n.length/2);
        for (int i = 0; i < n.length; i++) {
            int m = Math.abs(n[i]);
            if (n[m-1] < 0) {
                // 第m个已经是负数了, 说明是第二次遇到
                dups.add(m);
            } else {
                // 第一次遇到, 置为相反数
                n[m-1] = -n[m-1];
            }
        }
        System.out.format("nums: %s, dups: %s\n", Arrays.toString(n), dups);
        return dups;
    }

    // 交换法有问题
    public List<Integer> findDuplicates1(int[] n) {
        for (int i = 0; i < n.length; i++) {
            n[i]--;
        }

        List<Integer> dups = new ArrayList<>(n.length/2);

        int i = 0;
        while (i < n.length) {
            if (n[i] != i) {
                if (n[n[i]] == n[i]) {
                    // 这里有问题, 多次交换后, 可能会重复记录
                    if (dups.isEmpty() || dups.get(dups.size()-1) > i) {
                        dups.add(n[i] + 1);
                    }
                    i++;
                } else {
                    // swap
                    int t = n[n[i]];
                    n[n[i]] = n[i];
                    n[i] = t;
                }
            } else {
                i++;
            }
        }
        System.out.format("nums: %s, dups: %s\n", Arrays.toString(n), dups);
        return dups;
    }
}
